Sen(Qian)’s Memo

https://arxiv.org/abs/2111.00980

人間は類似したものから種類は不明だが、似ているものを発見できる。これは$k$クラスのデータで学習し、$k+1$クラスのデータを分類させるという問題=MPEにあたる。

この点から考えると、$k=1$とすればPU Learningといえる。

伝統的には、混合分布推定とは大量にUがある状態で、どのようなクラスタがありその分布とは何かを推定するもの。混合分布推定は高次元データにおいてはうまく働かず、PUについても同様な問題がある(データセット固有のものだけに性能が良いなど)

この論文では、Best Bin Estimation(BBE)というMPEで使われる有効なテクニックを応用し、Conditional Value Ignoring Risk(CVIR)について学習する。

この研究では高次元では使えないということで、何かしらの強い識別器の内部状態のベクトルを用いることでラベルシフトで使われるBBEの手法を使えるようにした。

PUにおける混合比では、完全にPとUが分離されていなければ理論的にはClass Priorを推定できると理論的にわかるが、そうでない場合はいろいろな仮定を設けないと本質的には推定できないとわかっている。

絶対に収束するとわかっている手法として以下のものがあるが、理論上であり実際は収束が非常に遅いことがある。

G. Blanchard, G. Lee, and C. Scott. Semi-supervised novelty detection. The Journal of Machine Learning Research, 11:2973–3009, 2010.

これについて、より早い収束ができるMPEアルゴリズムを提案されているが、高次元データでは性能が低いし大規模データセットにも弱い。

H. Ramaswamy, C. Scott, and A. Tewari. Mixture proportion estimation via kernel embeddings of distributions. In International conference on machine learning, pages 2052–2060, 2016.

似てる手法では、決定木を用いて入力空間内のサブドメインがあるが、これも高次元データに弱い。

J. Bekker and J. Davis. Estimating the class prior in positive and unlabeled data through decision tree induction. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.

Class Priorを推定するためにいったんPU識別器を訓練し、それから推定するというのもある(鶏先卵先問題)いずれも理論的保証がなかったり不安定だったり。

• ベクトル$\mathbf{v}$について、$\mathbf{v}_i$は$i$番目の成分だとする。
• データは$\mathbf{x} \in X \subseteq \mathbb{R}^d$である。
• Ground Truthのラベルは$Y = \{-1, +1 \}$である。
• Uデータは、Class Priorの$\pi = Pr(y=+1)$を用いて、$p_u(\mathbf{x}) = \pi p_p(\mathbf{x}) + (1 - \pi) p_n(\mathbf{x})$にとって構成されている。

MPEとは、Class Priorの$\pi$を推定する問題である。$p_p, p_n, p_u$について特段の条件がない限り、これはBlanchardにより一意には定まらないとわかっている。

導入したBBEという手法について説明する。

まず、ある固定されたPUデータで学習した識別器$f$があり、その内部状態のベクトルを状態として使う。

次に、$f$で確信をもってPであると判断するようなデータの割合を探す。理論的には以下のようになるが、実際は経験的に確信度が高いPのデータを選ぶかたちである。

BBEという手法は、Class Priorは、以下のように推定する。これは真のClass Priorに収束する。

それぞれ、$p_u$の分布において、ある$c$以上の信頼度(Pっぽい)のデータの割合と。$p_p$の分布においての$c$以上の信頼度のデータの割合の比である。この比を最小化できるような$c$を選べば、それがClass Priorになるという理屈。

理由として、ほぼほぼPであるとわかっているような領域(ここでは識別器が閾値$c$を超える)において、Uの中でこれを満たすデータはPと扱うことで、その割合がClass Priorとほぼ等しいと考えられる。

この時、分母の$q_p(c) \approx 1$になるが、これを1とは固定しない。なぜなら、使っているPUデータの識別器$f$について過学習したPのみ取り込んでしまい、本来のPの分布は得られないとわかる。

比率の最小値をとるのは以下の原因から。高すぎる$c$では$f$にOverfitした領域のみ着目されて、そこにあてはまるPのデータは本来よりは少なくなる(その結果分母が小さくなり比率が大きくなる)。低すぎる$c$ではそもそも領域がPの分布よりも広く、本来よりも多くのU内のサンプルをPと判定してしまい、比率が大きくなるから。

これは一般的なBest Bin Estimation(BBE)の考え方である。

1. ある$z \in [0, 1]$を与えられたら、経験的に$\hat{q}_u(z), \hat{q}_p(z)$を推定できる。
2. 以下の式を最小化するような$\hat{c} = c$である。
   1. 以下の式は凸関数なので、optimizerで最適な値を得られるとわかっている。
   2. ハイパーパラメタとして、$0 < \delta, 1 < \gamma$とする。

本来ならば1項目だけだが、後半の部分は理論的なリスク上界関係の式である。小さい正の定数$\gamma$にしている(0.001とか)。

推定の詳細はAppendixにある。必要ならまた読みに戻る。

nnPUから、Uの中からPをほぼ見つけられれば実質的にPNになるので、学びやすくなるだろう。これは、以下のself-supervised learningベースの手法=CVIRになる。

最初はPU Learning(nnPUなど)でwarm upして、次にCVIRで学習する。

具体的に記述すると以下のようになる。これがConditional Value Ignoring Risk(CVIR)

1. Training Dataの損失が収束するまで以下のループを回す。
   1. Uの中のすべてのデータについて、Unbiased EstimatorのU部分のRiskの式$l(f(\mathbf{x}), -1)$を計算し、その中で損失が低い順から$1 - \pi$の割合のデータを$X_n$と置いて、他を$X_p$にする。(Pseudo Label付与)
   2. $X_p, X_n$についてシャッフルして、Minibatch学習を行う。
      1. Minibatch$(X_p^i, X_n^i)$が得られる。
      2. これについて、PN LearningのようにClass Prior$\pi$を用いて学習をする。
2. これで学習したモデルがPU Learningの学習器。

これ、Self-supervised系あるあるのミスラベルの影響が積み重なるのやっぱかなりあるじゃないか…?

Transform Estimate Discardという統合したものを提案した。

1. PUデータをそれぞれ2つに分割する。$(X_p^1, X_u^1),(X_p^2, X_u^2)$である。
2. まず、$X_n^1 := X_u^1$として、PN Learningを行う。
   1. ミニバッチで学習し、目標関数は以下のようなもの。
   2. ここで重みが消えているが、どうやら分類可能である限り重みは重要ではないという先行研究があるらしい。
   $\mathbb{E}_P[l(f(\mathbf{x}), +1)] + \mathbb{E}_N[l(f(\mathbf{x}), -1)]$
3. 次に、PositiveをNegativeに分類する率と仮のNegativeをPositiveに分類してしまう率について、その総和が一定以下(つまり収束する)になるまでループを回す。
   1. Class Priorの$\pi$をBBEで推定する。
   2. CVIRのアルゴリズムで訓練する。

つまり、まずはPN LearningでWard upしてから、Class Priorの推定→CVIR(Self-supervised Learningベース)で訓練ということ。

CIFAR-10やMNISTを使用。Class Priorは0.5としている(CIFAR-10は犬vs猫)。ネットワーク構造はMLPやResNet18です。